#-*- encoding=utf-8 -*-

import copy
from collections import deque

#start_state -- 开始状态
#end_state -- 结束状态
#next_state -- 状态变迁函数 f: (state, position) ==> (state, position)
#next_position -- 确定下一次探索方向 f: (state, position) => position
#condition -- 状态约束条件 f: state ==> Ture/False
#solve -- 根据开始状态/结束状态/状态变迁函数/状态约束条件，返回根据深度优先搜索算法求解的状态变迁路径

def solve(start_state, end_state, next_state, next_position, constraint):
	visited_states = [] 				#记录访问过的状态，在状态解空间中搜索目标状态时不允许访问重复状态（去除循环）
	visiting_states = deque() 			#待访问状态列表，后进先出队列（堆栈）实现深度优先搜索算法，其元素为state，当栈顶为目标状态时，栈顶到栈底就是反向搜索路径
	visiting_states.append((start_state, None))	#把开始状态加入待访问状态队列
	visited_states.append(start_state) 		#加入到待访问队列的
	solved = False #结束搜索标志
	solution = []

	try_times = 0
	direction = 0
	state = start_state
	position = None
	while len(visiting_states) > 0:
		try_times += 1
		if state == end_state:
			break
		else:
			if direction == 0:
				s_next, p_next = next_state(state, position)
			else:
				position = next_position(state, position)
				if position is None:
					s_next, p_next = None, None
				else:
					s_next, p_next = next_state(state, position)

			if s_next is None:
				if p_next is None:
					(state, position) = visiting_states.pop()
				direction = 1
			elif constraint(s_next) and (s_next not in visited_states):
				visiting_states.append((s_next, p_next))
				visited_states.append(s_next)
				state, position = s_next, p_next
				direction = 0
			else:
				#继续探索(state, position)的下一个方向
				direction = 1
	print("try_times={}".format(try_times))
	for s, p in visiting_states:
		solution.append(s)
	return solution

def print_solution(solution):
	if len(solution) > 0:
		print("find a solution with {} steps: ".format(len(solution)), end='')
		for s in solution:
			print(" =>", s, end='')
		print()
	else:
		print("no solution found!!!")

def farmer_issue_constraint(state):
	#农夫不在时，狼会吃羊，羊会吃白菜
	fake_states = [['F','w','s','C'],['F','w','s','c'],['F','W','s','c'],['f','W','S','C'],['f','W','S','c'],['f','w','S','C']]
	return not(state in fake_states)

def farmer_issue_next_position(state, position):
	if position == None:
		position = 0

	if position + 1 >= len(state):
		return None
	else:
		return position + 1

def farmer_issue_next_state(state, position):
	#农夫一次只能带走一样东西过河
	if position == None:
		position = 0

	s = state[position]
	r = copy.deepcopy(state)
	for i in range(len(r)):
		if s == r[i]:
			#农夫不带任何东西过河
			if s == 'F':
				r[i] = 'f'
			elif s == 'f':
				r[i] = 'F'
			#农夫带狼过河
			elif s == 'W':
				r[i] = 'w'
			elif s == 'w':
				r[i] = 'W'
			#农夫带羊过河
			elif s == 'S':
				r[i] = 's'
			elif s == 's':
				r[i] = 'S'
			#农夫带白菜过河
			elif s == 'C':
				r[i] = 'c'
			elif s == 'c':
				r[i] = 'C'
		else:
			#农夫带东西过河时，自己也要过河
			if r[i] == 'F':
				r[i] = 'f'
			elif r[i] == 'f':
				r[i] = 'F'
	return r, 0

def solve_farmer_issue():
	#FWSC的顺序固定，大小写组合变化
	start_state = ['F', 'W', 'S', 'C'] 		#X--表示x在左岸，x--表示x在右岸, x的取值集合为(f,w,s,c)
	end_state = ['f', 'w', 's', 'c'] 		#f--代表farmer，w代表wolf，s代表sheep，c代表cabbage
	solution = solve(start_state, end_state, farmer_issue_next_state, farmer_issue_next_position, farmer_issue_constraint)
	print_solution(solution)

def hano_issue_next_position(state, position):
	if position == None:
		(source, dest) = (0, 1)
	else:
		(source, dest) = position

	dest = dest + 1
	if dest >= 3:
		dest = 0
		source = source + 1
		if source >= 3:
			return None
		elif source == dest:
			return hano_issue_next_position(state, (source, dest))
	return source, dest

def hano_issue_next_state(state, position):
	if position == None:
		(source, dest) = (0, 1)
	else:
		(source, dest) = position

	if len(state[source]) > 0:
		next_state = copy.deepcopy(state)
		next_state[dest].append(next_state[source].pop())
		return next_state, (0, 1)
	else:
		return None, position

def is_sorted(array):
	i = 0
	n = len(array) - 1
	while i < n:
		if array[i] < array[i+1]:
			return False
		i = i + 1
	return True

def hano_issue_constraint(state):
	for array in state:
		if not is_sorted(array):
			return False
	return True

def solve_hano_issue():
	start_state = [[8, 7, 6, 5, 4, 3, 2, 1], [], []]
	end_state = [[], [], [8, 7, 6, 5, 4, 3, 2, 1]]
	solution = solve(start_state, end_state, hano_issue_next_state, hano_issue_next_position, hano_issue_constraint)
	print_solution(solution)

if __name__ == '__main__':
	solve_farmer_issue()
	solve_hano_issue()
